Computer networks, i.e. interconnected collections of autonomous computers, provide a variety of services such as electronic mail and fie transfer services. FIG. 1 illustrates the structure of a typical computer network. The first part of the network typically comprises a collection of Machines 102, called hosts, intended for running application programs. The network also includes Communication Subnet 104 linking the hosts. The subnet's job is to carry messages from host to host. The subnet typically comprises two basic components: Switching Elements (or Interface Message Processors, IMPs) 106 and Transmission Lines 108. Each host is connected to one, or occasionally several, IMPs.
Modem Computer networks are typically designed in a highly structured way. To reduce design complexity most computer networks are organized as a series of layers. For example, the Reference Model of Open Systems Interconnection developed by the International Standards Organization (ISO) is a seven layer model. A network architecture based on this model is illustrated in FIG. 2. See, Andrew S. Tanenbaum, Computer Networks, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1981.
Computers communicate among themselves in the network to provide services by sending sets of signals to one another over computer networks. The interplay of these signals forms a "protocol" and enables layer n on one machine layer to communicate with layer n in another machine. The purpose of each layer is to offer certain services to higher layers, shielding those higher layers from the details of how the offered services are actually implemented. The entities comprising the corresponding layers on different machines are called peer processes or peer layers. This is a virtual communication since only at the lowest layer is there a physical connection. Adjacent layers communicate through interfaces. The interface defines which primitive operations and services the lower layer offers the higher layer.
A computer protocol must be clearly specified to enable the respective computers on the network to be able to efficiently communicate. When a protocol is implemented in a manner that is different from how it is specified, the respective machines using the protocol will be unable to communicate meaningfully. Protocol standards are typically defined by bodies such as the ISO and CCITT. A method used to implement a protocol in a computer network is illustrated in FIG. 3. Typically in first step 301, a protocol is described in English with perhaps some computer code or diagrams. The protocol of first step 301 must then be specified in a formal computer language. For example, the protocol may be specified in a language called the Protocol Specification Language (PSL) which is similar to a subset of the CCITT recommended Specification Description Language (SDL). In both PSL and SDL a protocol is specified as a collection of communicating finite state machines as indicated in step 303. Once specified in a computer language, the protocol may be processed by a compiler as shown in step 305, as for example from PSL to C code, and the code is then implemented in the network as illustrated in step 307.
More particularly, the protocol is used to generate a precise description (called a formal specification) of the protocol represented as a collection of communicating processes. Each process, represented as a finite state machine (FSM) communicates with other FSMs through input/output (i/o) operations as defined by the specification. An output operation in a process must have a corresponding input operation in another process, and vice,versa. An FSM representation of a protocol specification consists of a set of states, including an initial state, outputs, inputs, next state function, and output function. A state is defined as a stable condition where the FSM rests until an input is applied. The next state function and output function define the state to which an FSM moves and the output it generates after an input is applied. In PSL, for example, a protocol FSM representation may be specified as an input file comprising process definition statements for naming processes; declaration statements specifying the inputs, outputs, states and initial state of a process FSM; and statements defining the transitions that take place when the specified input or output operation occurs. It is convenient to use a directed graph, called a state diagram, to describe the behavior of an FSM. FIG. 3A illustrates an FSM. The directed graph or FSM comprises states or vertices 322 which represent the FSM states and directed edges 324 which represent transitions between states. Each directed edge 324 is labeled with a notation of i/o operations 326 to specify transitions between states 322, and the directed edge points to the next state the entity assumes when the proper input is received.
Before an implementation of a protocol is incorporated into a computer network, it is advantageous to test that the hardware, software, and/or firmware implementation of the protocol conforms to the specification or standard. FIG. 4 illustrates a block diagram for conformance testing. Input signals (i.e. a test sequence or sequence of signals) are applied to specification 406 to generate a first output and to implementation 403 to generate a second output. The outputs of specification 406 and implementation 403 are then compared in fault detector 409. If the outputs are not identical, a fault signal is generated. Analysis of the errors in the output can often detect not only that the implementation is incorrect but also what specific part of the implementation is in error, i.e., it may be used as a diagnostic tool. When a protocol is simple, conformance testing is not a problem. However, when the services provided by a computer network increase, the complexity of the computer protocols typically increases making conformance testing problematic.
The dominant schemes in testing FSMs, such as those used to represent protocols, are structured, such as checking sequences, etc., which are appropriate for testing a single isolated machine. See, F. C. Hennie, "Fault-detecting Experiments for Sequential Circuits," Proc. 5th Ann. Symp. on Switching Circuit Theory and Logical Design, pp. 95-110, November 1964; K. K. Sabnani and A. T. Dahbura, "A Protocol Testing Procedure," Computer Networks, pp. 285-297, Vol. 15, No. 4, 1988; A. V. Aho, A. T. Dahbura, D. Lee, and M. U. Uyar, "An Optimization Technique for Protocol Conformance Test Generation Based on UIO Sequences and Chinese Postman Tours," IEEE Trans. Comm., vol. 39, no. 11, pp. 1604-1615, November 1991. Mihalis Yannakakis and David Lee, "Testing Finite State Machines," Proceedings of the 23rd Annual ACM Symposium of Theory of Computing, New Orleans, May 1991, pp. 476-485. In structured testing, a test based on the structure of the FSMs is designed. However, for protocols specified by communicating FSMs, the size of the structure of the composite machine is formidable thus making structured test generation impractical.
A variety of approaches have been used for conformance testing in which test sequences can be generated that provide good fault coverage, i.e. that exercise all parts of the protocol implementation, with one-third the length of those generated by ad hoc methods. K. K. Sabnani and A. T. Dahbura, "A Protocol Testing Procedure," Computer Networks, pp. 285-297, Vol. 15, No. 4 (1988); A. V. Aho, A. T. Dahbura, D. Lee and M. U. Uyar, "An Optimization Technique for Protocol Conformance Test Generation Based on UIO Sequences and Chinese Postman Tours," IEEE Trans. Comm., vol. 39, no. 11, pp. 1604-1615, November 1991. However, these techniques require that the protocol entity under test be modeled at a fairly high level of abstraction as one deterministic finite state machine. Another method of conformance testing involves composing the communicating FSMs into one machine and generating a transition tour of the composed machine. This method also has limitations in that the procedure encounters two obstacles: 1) the well-known state explosion problem, and 2) the fact that internal transitions cannot be fully tested since they are not observable by a tester. Other testing approaches note that an implementation conforms to a specification if both of them can generate the same infinite random trace. This is possible if any only if they have observational equivalence. R. Milner, Communication and Concurrency, Prentice Hall, Inc., Englewood Cliffs, N.J., 1989. However, testing conformance by ensuring observational equivalence is complex since there are internal transitions, which are not observable and the behavior of the machines can be nondeterministic.
To detect faults in a protocol implementation, a minimal requirement is to traverse each transition in FSM representation of the protocol at least once. This is a difficult problem because of the well-known state explosion problem. Additionally, some observations have been made about the reachability of FSMs:
1. The following problems are PSPACE-complete: (i) Is a state or a transition of a component machine reachable from the initial state? (ii) Is a state or transition of the composite machine reachable from the initial state? See, M. R. Garey and D. S. Johnson, "Computers and Intractability--A Guide to the Theory of NP-Completeness," W. H. Freeman and Company, New York, 1979. PA1 2. The following problems are PSPACE-complete as a corollary to the first observation: (i) Given two states of a component machine, is one state reachable from the other through internal transitions only? (ii) Given two states of the composite machine, is one state reachable from the other through internal transitions only?
The above observations show the inherent limitation of testing communicating FSMs even in terms of testing each component machine. In the worse case, to construct a checking or input sequence (or even a covering path) of a component machine can take exponential time. In practice, this is out of the question. Furthermore, due to nondeterministic behavior of the machines, the problem becomes undecidable unless some fairness assumptions are made. In addition, there are internal transitions, which can never be observed and be verified to be tested. Therefore, conventional methods of testing a (single) FSM are not applicable for communicating FSMs. Thus them is a need for a method and apparatus for conformance testing of protocols specified a communicating FSMs that generate test sequences with high fault coverage and short sequence length.